1. Field of the invention
The subject of the present invention is a method for controlling the program execution integrity by verifying execution trace prints.
2. Description of the Prior Art
It applies in particular to controlling the integrity of program execution, said program execution updating a trace print representing the execution pathway and/or handled data, bearing in mind that at determined points of the program the current trace print value is compared with an expected value.
Some small, embedded systems, such as smart cards for example, are designed to protect the data and programs they contain. In particular the material substrate of these systems makes it very difficult to observe and modify stored data, including at the time of program execution.
Protection is not total however. These systems may be exposed to malicious action (also called  attacks ) intended to deteriorate the proper functioning of the system and programs, or to unmask confidential information. Physical attacks (also called material attacks) are electric supply disturbances for example, radiation bombardment, the destruction of logic gates, etc.
Said attacks may lead to ill-functioning of the program executed on the card: the instructions and data read from the memory may be incorrect, and the processor may inaccurately execute some instructions. Said disturbances may render invalid a code which checks the security conditions before performing certain sensitive actions.
Let us suppose the following (simplified) example of a code written in language C:
if(!condition 1( ))goto error;if(!condition2( ))goto error;do_sensitive_action( );The sensitive action  do-sensitive-action( ) is normally only executed if the two conditions  condition1( ) and  condition2( ) are met. Nonetheless, physical disturbances may cause the processor to jump directly over the code of the two  ifs or to read from the memory a series of different instructions of the code of the two  ifs . In this case, the processor may execute  do-sensitive-action( ) even if the tests  condition1( ) and  condition2( ) have not been met.
One technique known to  harden a program against this type of attack consists of introducing redundancy between the program check flow and the values of certain auxiliary variables. In other words, auxiliary variables are used to keep a trace of the fact that execution has indeed passed through all checks of security conditions. In the case of the above example, it could be written as follows:
trace=0;if(condition1( )trace| =1;else goto error;if(condition2( )trace| =2;else goto error;if(trace== 3) do_sensitive_action( );Hence, if the first two  ifs are not correctly executed, there is a strong chance that the  trace variable does not equal 3 at the end, and therefore that the action  do-sensitive_action( ) is not executed.
Even in this case, a disturbance could cause the test  trace==3 to be true at all times or to be ignored also. As a general rule, for the relevance of the invention disclosed herein, it is assumed that disturbances caused by physical attacks are relatively unrefined; they can inactivate the execution of part of the program or change the apparent content of part of the memory, but the extent of this part is not finely controlled by the attacker.
This approach can be generalized as follows. The program updates a value representing important control points through which its execution passes. This value can be a trace print e.g. a checksum calculated on integers which characterize these important control points. Before executing a sensitive operation, this value updated during execution may be compared with its normal (expected) value, manually pre-calculated by the programmer from the control structure of the program. For example:
trace = 42:for(i = 0;i<4;i++) {  if(provided_pin[i]!=actual_pin[i]goto error;  trace = h(trace,i);}if(trace== 2346)do_sensitive_action( );It is to be noted however that a PIN code is not usually checked in this way; this is merely an example to illustrate the use of trace print calculation.
The tracing print operator used here is the linear congruency  h(t,x)=((33*t) mod(2^16)) xor x in which:                 a*b represents the product of  a by  b ,         a mod b represents the remainder of the division of  a by  b (i.e. the modulo);         a^b represents the raising of  a to power  b ,         a xor b is the operation  or exclusive logic on the bits representing  a and  b .        
The value 2346 is no other than  h(h(h(h(42,0), 1), 2), 3) i.e. the trace print of normal execution of the loop (4 turns per  i variant of 0 to 3). If the loop is not executed or if it finishes abnormally before making 4 turns, the value of the  trace variable before the  do_sensitive_action( ) call will most probably be different from 2346.
This tracing print operator “h” can be seen as an operator which allows incremental calculation of a tracing print function “H” which operates on sequences of integers which characterize said important control points. This tracing print function on the observation sequences is defined by:  H(T0, i1, i2, . . . , in)=h( . . . h(h(T0, i1), i2) . . . , in) .
So that it can be used in small embedded systems having low calculating capacity, the  h tracing print operator must be quick to calculate. Also, the resulting  H tracing print function must be preimage resistant: the probability that the trace print  H(T0, i1, . . . , in) of a random sequence  T0, i1, . . . , in equals a given value must be low (in the order of 2−B where B is the number of bits to encode the trace print value).
In some cases described below, it may also be helpful to have a tracing print operator  h which is invertible in its first argument: for all values  t′ and  x ,  t exists such that  t′=h(t, x) .
It is possible for example to use a linear congruency for  h , as is the case in the example given above. This linear congruency also has the property of being invertible. More generally, any function can be used which combines the following operations: addition, subtraction or exclusive logic (xor) with a constant or with  x , rotation of a constant number of bits; multiplication by an uneven constant.
It is also possible to use a cyclic redundancy check function (CRC) such as CRC-16; said function can be calculated efficiently using pre-calculated tables.
On the other hand, even if a checksum (defined as the sum of integers which have matched arguments) does have good properties of rapid calculation, preimage resistance and invertibility, it is little satisfactory since the tracing print function obtained is insensitive to the order of arguments.
At the other end of the spectrum there are cryptographic tracing print functions (digests such as SHA-1, MD-5, etc) which are very secure but also very costly to calculate.
Trace print setting can be made by means of two main operations of trace print assignment and trace print updating:  setTrace(T) fixes the initial value of the trace print at  T (typically any value), and “addTrace(N)” adds an integer “N” to the trace that is characteristic of an observation of program execution. In the above example,  setTrace(T) corresponds to the assignment  trace=T ; and  addTrace(N) corresponds to update of the trace print by  trace=h(trace,N) .
The value “N” supplied during an operation  addTrace(N) can itself be the result of a tracing print function. The more the integer  N is representative of local execution of the program, i.e. the more  N varies in the presence of a possible execution disturbance, the better the detecting power of an attack.
Trace print controlling can be made using a single operation:  checkTrace(T) checks that the current value of the trace print is indeed  T . If not, it is an indication that the program has undergone attack. Strictly speaking, systems such as smart cards wear out and a trace print difference could also be the sign of a material fault.
At all events, the program can no longer provide the service for which it was designed. In critical systems, the measures taken under such circumstances typically consist of securitizing some program data and interrupting program execution whether definitively or not. When materially possible, a sound or visual signal could alert the user of the ill-functioning.
In the light of the above example, it is obvious that the implementing of this technique requires much effort on the part of the programmer, firstly to insert the calculation steps of the trace print, and secondly to calculate the expected trace print values at the points where it is to be checked.